package com.shm.leetcode;

/**
 * 214. 最短回文串
 * 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
 *
 * 示例 1:
 *
 * 输入: "aacecaaa"
 * 输出: "aaacecaaa"
 * 示例 2:
 *
 * 输入: "abcd"
 * 输出: "dcbabcd"
 * @author SHM
 */
public class ShortestPalindrome {
    /**
     * 方法二：反转+equals
     * 思路：方法一超时了，没办法只能去看官方，hash、kmp。。。没耐心看下去。cv?拒绝！hash让我灵机一动想到了equals，这不就是现成的hash算法吗？虽然和官方的不是一回事，但我认定就是它了。判断回文时字符逐个判断效率太低，改为先将s_prefix反转得到s_prefix_rev，然后s_prefix.equals(s_prefix_rev)，机智。
     * 结果：超时 /(ㄒoㄒ)/~~
     *
     * 方法三：没名
     * 思路：唯一还可以优化的地方就是反转操作了，每个s_prefix都要反转太耗时了。想想其实不用每个都进行反转，只需要开始将s进行反转得到s_rev，因为所有s_prefix_rev读包含在s_rev里面，我只需要substring取相应的字串就ok。
     *
     * 作者：shi-san-dao
     * 链接：https://leetcode-cn.com/problems/shortest-palindrome/solution/si-xing-dai-ma-jie-jue-by-shi-san-dao/
     * @param s
     * @return
     */
    public String shortestPalindrome(String s) {
        String ss = s+ new StringBuffer(s).reverse().toString();
        for (int i=s.length(),j=i;i>0;i--,j++){
            if (ss.substring(0,i).equals(ss.substring(j))){
                return ss.substring(s.length(),j)+s;
            }
        }
        return "";
    }
}
